#include <iostream>
#include <ctime>
#include <vector>

int num = 0;

// 指数级时间复杂度 存在大量重复计算
int fib(int n){
	num++;
	if(n == 0) return 0;
	if(n == 1) return 1;
	return fib(n-1) + fib(n-2);
}

using namespace std;

int main(){
	num = 0;
	int n = 42;
	time_t startTime = clock();
	int res = fib(n);
	time_t endTime = clock();
	
	cout << "fib(" << n << ") = " << res << endl;
    cout << "time : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
    cout << "run function fib() " << num << " times." << endl;
}
